#include<iostream>
#include<vector>
using namespace std;

// 输出幂集
void disp(vector<vector<int>> ans)
{
	printf("    ");
	
	// 遍历打印
	for(auto it=ans.begin(); it!=ans.end(); it++)
	{
		if((*it).size()==0)
			printf("[]  ");
		else
		{
			printf("[");
			for(int j=0; j<(*it).size(); j++)
				if(j==0)
					printf("%d",(*it)[j]);
				else
					printf(" %d",(*it)[j]);
			printf("]  ");
		}
	}
	printf("\n");
}

// 向Mi_1中每个集合元素末尾添加i
vector<vector<int>> appendi(vector<vector<int>> Mi_1, int i)
{
	vector<vector<int>> Ai = Mi_1;
	for(int j=0; j<Ai.size(); j++)
		Ai[j].push_back(i);

	return Ai;
}

// 迭代算法 -- 求幂集
vector<vector<int>> subsets1(int n)
{
	// 存放{1-n}的幂集
	vector<vector<int>> Mi;
	
	// 辅助
	vector<vector<int>> Mi_1={{},{1}};
	
	for(int i=2; i<=n; i++)
	{
		// 向Mi_1中每个集合元素末尾添加i
		vector<vector<int>> Ai = appendi(Mi_1, i);
		Mi = Mi_1;
		
		// 将Ai所有集合元素添加到Mi中
		for(int j=0; j<Ai.size(); j++)
			Mi.push_back(Ai[j]);
		Mi_1 = Mi;
	}
	return Mi;
}

// 递归算法 -- 求幂集
vector<vector<int>> pset(int n, int i)
{
	if(i==1)
		return {{}, {1}};
	
	else
	{
		// 递归求出Mi_1 
		vector<vector<int>> Mi_1 = pset(n, i-1);
		
		// Mi置为Mi_1
		vector<vector<int>> Mi = Mi_1;
		vector<vector<int>> Ai = appendi(Mi_1, i);
		
		// 将Ai所有集合元素添加到Mi中
		for(int j=0; j<Ai.size(); j++)
			Mi.push_back(Ai[j]);
		
		// 返回Mi 
		return Mi;
	}
}

// 递归算法 -- 求幂集
vector<vector<int>> subsets2(int n)				
{
	return pset(n, n);
}

int main()
{
	int n=3;
	
	// 存储幂集的矩阵
	vector<vector<int>> ans;
	printf("{1-%d}的幂集如下:\n", n); 
	
	printf("解法1\n"); 
	ans = subsets1(n);
	disp(ans); // 打印结果
	
	printf("解法2\n"); 
	ans = subsets2(n);
	disp(ans); // 打印结果
	
	return 0;
}
